#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

//交错字符串
//https://leetcode.cn/problems/interleaving-string/description/
// class Solution {
// public:
//     bool isInterleave(string s1, string s2, string s3) {
//         int m = s1.size();
//         int n = s2.size();
//         if(m+n!=s3.size()) return false;

//         //vv[i][k] 表示 s1[0,i] 和 s2[0,k] 组合能否拼接成s3[0,i+k+1]
//         vector<vector<bool>> vv(m+1,vector<bool>(n+1));

//         //初始化
//         //s1和s2都为空时vv[0][0]=true
//         //当s1 为空 s2和s3 匹配 当s2[i]!=s3[k]时，后面都是false
//         //同理，s1和s3匹配，s2为空也是如此

//         vv[0][0] = true;
//         for(int i = 1;i<=m;++i)
//             if(s1[i-1] == s3[i-1]) vv[i][0] = true;
//             else break;

//         for(int i = 1;i<=n;++i)
//             if(s2[i-1] == s3[i-1]) vv[0][i] = true;
//             else break;

//         for(int i = 1;i<=m;++i)
//             for(int k = 1;k<=n;++k)
//                 //当s2[k]为结尾时 只需要s1[0,i]和s2[0,k-1]可以组成s3[0,i+k]即可
//                 vv[i][k] = (s2[k-1] == s3[i+k-1] && vv[i][k-1]) 
//                 //反之就是s1[i]为结尾
//                 || (s1[i-1] == s3[i+k-1] && vv[i-1][k]);
            
//         return vv[m][n];
//     }
// };


//两个字符串的最小ASCII删除和
//https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/description/
// class Solution {
// public:
//     int minimumDeleteSum(string s1, string s2) {
//         int m = s1.size();
//         int n = s2.size();

//         //vv[i][k] 表示以s1[0,i] 和 s2[0,k]区间中 两字符串最大子序列的ASCII最大和

//         vector<vector<int>> vv(m+1,vector<int>(n+1));

//         for(int i = 1;i<=m;++i)
//             for(int k = 1;k<=n;++k)
//             {
//                 //当s[i] == s[k] 时 子序列同时以两个字符串的字母为结尾
//                 //只需要vv[i-1][k-1]+s[i]即可
//                 //当只以s1[i]为结尾时 vv[i][k-1]
//                 //当只以s2[k]为结尾时 vv[i-1][k]
//                 //当都不以s1[i]和s2[k]为结尾时 vv[i-1][k-1]
//                 //其中vv[i][k-1]和vv[i-1][k]包含vv[i-1][k-1]的情况 可以省略判断
//                 vv[i][k] = max(vv[i-1][k],vv[i][k-1]);
//                 if(s1[i-1] == s2[k-1]) vv[i][k] = max(vv[i][k],vv[i-1][k-1]+s1[i-1]);
//             }

//         int sum = 0;
//         //我们统计的是两个字符串的最大子序列和 用总和减去2倍最大和剩下的就是最小和
//         for(const auto& c:s1) sum+=c;
//         for(const auto& c:s2) sum+=c;
//         return sum-(2*vv[m][n]);

//     }
// };


//最长重复子数组
//https://leetcode.cn/problems/maximum-length-of-repeated-subarray/submissions/
// class Solution {
// public:
//     int findLength(vector<int>& nums1, vector<int>& nums2) {
//         int n1 = nums1.size();
//         int n2 = nums2.size();

//         //vv[i][k] 表示以nums1[i]和nums2[k]数字为为结尾时最大子数组长度

//         vector<vector<int>> vv(n1+1,vector<int>(n2+1));

//         int maxn = 0;
//         for(int i = 1;i<=n1;++i)
//             for(int k = 1;k<=n2;++k)
//             {
//                 if(nums1[i-1] == nums2[k-1]) vv[i][k] = vv[i-1][k-1]+1;
//                 maxn = max(maxn,vv[i][k]);
//             }

//         return maxn;
//     }
// };